{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   }
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        if not m:\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        max_area = 0\n",
    "        count = 0\n",
    "        visitor = [[False] * n for i in range(m)]\n",
    "        d = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        def in_area(i: int, j: int):\n",
    "            \"\"\"是否在区域内\"\"\"\n",
    "            return i >= 0 and j >= 0 and i < m and j < n\n",
    "\n",
    "        times = 0\n",
    "\n",
    "        def helper(x: int, y: int):\n",
    "            \"\"\"x,y 表示坐标\n",
    "            \"\"\"\n",
    "            nonlocal max_area, times, count\n",
    "            # print(x, y, count)\n",
    "\n",
    "            max_area = max(max_area, count)\n",
    "\n",
    "            for c in d:\n",
    "                new_x = x + c[0]\n",
    "                new_y = y + c[1]\n",
    "                # count = count + 1\n",
    "                if (\n",
    "                    in_area(new_x, new_y)\n",
    "                    and not visitor[new_x][new_y]\n",
    "                    and grid[new_x][new_y] == 1\n",
    "                ):\n",
    "                    count += 1\n",
    "                    visitor[new_x][new_y] = True\n",
    "                    helper(new_x, new_y)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not visitor[i][j]:\n",
    "                    visitor[i][j] = True\n",
    "                    count = 1\n",
    "                    helper(i, j)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "把grid的元素置0表示访问过！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        if not m:\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        max_area = 0\n",
    "        d = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        def in_area(i: int, j: int):\n",
    "            \"\"\"是否在区域内\"\"\"\n",
    "            return i >= 0 and j >= 0 and i < m and j < n\n",
    "\n",
    "        def helper(x: int, y: int):\n",
    "            \"\"\"x,y 表示坐标\n",
    "            \"\"\"\n",
    "            \n",
    "            if not in_area(x, y) or grid[x][y] != 1:\n",
    "                return 0\n",
    "            print(x, y)\n",
    "            grid[x][y] = 0\n",
    "            res = 1\n",
    "            for c in d:\n",
    "                new_x = x + c[0]\n",
    "                new_y = y + c[1]\n",
    "\n",
    "                res += helper(new_x, new_y)\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max_area = max(helper(i, j), max_area)\n",
    "        return max_area"
   ]
  }
 ]
}